package leetcode.top100;


import utils.ListNode;

import java.util.Stack;

/**
 * 判断是否是回文链表。
 * <p>
 * 方式1：使用栈，时空O(n)
 * <p>
 * 方式2：快慢指针：
 * <p>
 * 遍历链表一半的时候， 把后一半反转。时间O(n),空间O(1)
 *
 * @since 2019/12/18 0018 下午 5:52
 */
public class Code234_PalindromeList_回文链表 {


    //方式2：在链表中间位置【奇数个就是中心，偶数个是前一个】对链表进行翻转。
    //注意要翻转回去。时间O(n),空间O(1)
    private static boolean process(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
//        while(fast != null && fast.next != null && fast.next.next != null){
        //fast.next.next != null,而fast= fast.next.next确保了fast也可能是null
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //slow必定在中间， 把slow之后的反转
        ListNode pre = null;
        while (slow != null){
            fast = slow.next;
            slow.next = pre;
            pre = slow;
            slow = fast;
        }
        //记录链表尾巴，判断完成后好反转
        fast = pre;
        //pre现在是链表尾巴。从头到尾和从尾到头一起走
        slow = head;
        while(slow != null && pre != null){
            if(slow.val != pre.val) return false;
            slow = slow.next;
            pre = pre.next;
        }
        return true;
        //下面进行链表反转回去。这题没有要求。面试时问面试官是否需要
       /* pre = null;
        while(fast != null){
            slow = fast.next;
            fast.next = pre;
            pre = fast;
            fast = slow;
        }*/

    }
    //方式1：时空都是O(n)，把链表入栈，然后弹出。弹出的时候和遍历链表的值一样
    private static boolean process1(ListNode head){
        Stack<Integer> stack = new Stack<>();
        ListNode cur = head;
        while (cur != null){
            stack.push(cur.val);
            cur = cur.next;
        }
        cur = head;
        while(!stack.isEmpty()){
            if(stack.pop() != cur.val) return false;
            cur = cur.next;
        }
        return true;
    }
}
